package com.promote.algorithm;

/**
 * @ClassName IsPalindrome
 * Description 验证回文串
 * @Author LiZiHao
 * Date 2022/3/12 23:50
 * @Version 1.0
 **/
public class IsPalindrome {


    public class ListNode {
        int val;
        IsPalindrome.ListNode next;

        ListNode() {
        }

        ListNode(int val) {
            this.val = val;
        }

        ListNode(int val, IsPalindrome.ListNode next) {
            this.val = val;
            this.next = next;
        }
    }

    public boolean isPalindrome(String s) {

        if (s.length() == 0) {
            return true;
        }

        int left = 0, right = s.length() - 1;

        while (left < right) {

            //过滤不是字母和数字的字符
            while (left < right && !Character.isLetterOrDigit(s.charAt(left))) {
                left++;
            }
            while (left < right && !Character.isLetterOrDigit(s.charAt(right))) {
                right--;
            }

            if (Character.toLowerCase(s.charAt(left)) != Character.toLowerCase(s.charAt(right))) {
                return false;
            }
            left++;
            right--;
        }
        return true;
    }

    /**
     * 回文链表
     * 单向链表，只能从前往后访问，不能从后往前访问，所以使用判断字符串的那种方式是行不通的。
     * 但我们可以通过找到链表的中间节点然后把链表后半部分反转（关于链表的反转可以看下432，剑指 Offer-反转链表的3种方式），最后再用后半部分反转的链表和前半部分一个个比较即可。
     * @param head
     * @return
     */
    public boolean isPalindrome(ListNode head) {
        ListNode fast = head, slow = head;

        //通过快慢指针找到中点
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
        }

        //如果fast不为空，说明链表的长度是奇数
        if (fast != null) {
            slow = slow.next;
        }
        //反转后半部分链表
        slow = reverse(slow);

        fast = head;
        while (slow != null) {
            //判断节点值是否相同
            if (fast.val != slow.val) {
                return false;
            }
            fast = fast.next;
            slow = slow.next;
        }
        return true;
    }

    //反转链表
    private ListNode reverse(ListNode head) {
        ListNode prev = null;
        while (head != null) {
            ListNode next = head.next;
            head.next = prev;
            prev = head;
            head = next;
        }
        return prev;
    }
}
